package outoforder.leetcode01;

import org.junit.Test;

import java.util.ArrayDeque;

/**
 * @author shhjiang_001
 * @create 2020-07-10 22:46
 */

// 使用单调队列
public class Solution239 {
    public int[] maxSlidingWindow(int[] nums, int k) {
        ArrayDeque<Integer> deque = new ArrayDeque<>();
        int length = nums.length;
        int[] res = new int[length - k + 1];
        for (int i = 0; i < length; i++) {
            if (i < k-1){
                while (!deque.isEmpty() && nums[i] > deque.peek()){
                    deque.pop();
                }
                deque.push(nums[i]);
            }else {
                while (!deque.isEmpty() && nums[i] > deque.peek()){
                    deque.pop();
                }
                deque.push(nums[i]);
                if (!deque.isEmpty() && i>=k && nums[i-k]==deque.getLast()){
                    deque.removeLast();
                }
                res[i-k+1] = deque.getLast();

            }
        }
        return res;
    }
    @Test
    public void test(){
        maxSlidingWindow(new int[]{1,3,-1,-3,5,3,6,7},3);
    }
}
